﻿using UnityEngine;
using System.Collections;

public interface CompareAB<T>
{
    bool GreaterThan(T b);
    bool LessThan(T b);
}


public class PriorityQueue<T> where T: CompareAB<T>, new() {
    private T [] lst;
    private int heap_size;
    private bool is_max_heap;

    public PriorityQueue(int length,bool max_heap)
    {
        lst = new T[length];
        heap_size = 0;
        this.is_max_heap = max_heap;
    }

    public int Length
    {
        get { return this.lst.Length; }
    }

    public int GetHeapSize()
    {
        return this.heap_size;
    }

    private int LeftChild(int index)
    {
        return 2 * index;
    }

    private int RightChild(int index)
    {
        return 2 * index + 1;
    }

    private int Parent(int index)
    {
        return index / 2;
    }

    private void MinMax_Heapify(int index)
    {
        int lc_index = LeftChild(index);
        int rc_index = RightChild(index);
        int largest_index = index;

        if (this.is_max_heap == true)
        {
            if (lc_index <= this.heap_size && this.lst[lc_index].GreaterThan(this.lst[largest_index]))
            {
                largest_index = lc_index;
            }

            if (rc_index <= this.heap_size && this.lst[rc_index].GreaterThan(this.lst[largest_index]))
            {
                largest_index = rc_index;
            }
        }
        else
        {
            if (lc_index <= this.heap_size && this.lst[lc_index].LessThan(this.lst[largest_index]))
            {
                largest_index = lc_index;
            }

            if (rc_index <= this.heap_size && this.lst[rc_index].LessThan(this.lst[largest_index]))
            {
                largest_index = rc_index;
            }
        }
       
        if (largest_index != index)
        {
            T temp = this.lst[index];
            this.lst[index] = this.lst[largest_index];
            this.lst[largest_index] = temp;

            this.MinMax_Heapify(largest_index);
        }
    }

    public void BuildMinMax_Heap()
    {
        for (int i = this.heap_size/2; i >= 1; i--)
        {
            this.MinMax_Heapify(i);
        }
    }

    public T Heap_Minimum_Maximum()
    {
        return this.lst[1];
    }

    public T Extract_Minimum_Maximum()
    {
        T temp = this.lst[1];
        this.lst[1] = this.lst[this.heap_size];
        this.heap_size--;
        this.MinMax_Heapify(1);
        return temp;
    }

    public void Insert(T node)
    {
        if (this.heap_size >= this.Length)
        {
            AutoDilatation();
        }
        this.heap_size++;
        this.lst[this.heap_size] = node;


        int parent_index = this.LeftChild(this.heap_size);
        int cur_index = this.heap_size;
        

        if (this.is_max_heap == true)
	    {
            while (parent_index >= 1 && !this.lst[parent_index].GreaterThan(this.lst[cur_index]) )
            {
                T temp = this.lst[parent_index];
                this.lst[parent_index] = this.lst[cur_index];
                this.lst[cur_index] = temp;

                cur_index = parent_index;
                parent_index = this.Parent(cur_index);
            }
	    }
        else
        {
            while (parent_index >= 1 && !this.lst[parent_index].LessThan(this.lst[cur_index]))
            {
                T temp = this.lst[parent_index];
                this.lst[parent_index] = this.lst[cur_index];
                this.lst[cur_index] = temp;

                cur_index = parent_index;
                parent_index = this.Parent(cur_index);
            }
        }
        

    }

    public void AutoDilatation()
    {
        int newLength = (int)(this.Length * 1.5);
        T[] newLst = new T[newLength];
        for (int i = 1; i < this.Length; i++)
        {
            newLst[i] = this.lst[i];
        }

        this.lst = newLst;
    }
}
